package com.leetcode;


/**
 * 1043. 分隔数组以得到最大和 (中等)
 * 给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
 * 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
 */
public class LeetCode1043 {

    public static void main(String[] arg0) {
        int[] data = new int[]{1,4,1,5,7,3,6,1,9,9,3};
        System.out.println("分隔数组以得到最大和 = " + maxSumAfterPartitioning(data, 4));
    }

    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length + 1];
        dp[0] = 0;
        dp[1] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int maxK = arr[i];
            for (int j = i; j >= 0 && j > i - k; j--) {
                maxK = Math.max(maxK, arr[j]);
                dp[i + 1] = Math.max(dp[i + 1], dp[j] + maxK * (i - j + 1));
            }
        }
        return dp[arr.length];
    }
}
